package com.tgy.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: tgy
 * @Date: 12/8/20 11:47 AM
 *
 * https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/
 *
 */
public class _剑指_Offer_48_最长不含重复字符的子字符串 {

    public int lengthOfLongestSubstring(String s) {

        if (s == null || s.length() == 0) {

            return 0;
        }

        if (s.length() == 1) {

            return 1;
        }

        char[] chars = s.toCharArray();
        // 判断当前字符之前的字符串中与当前字符相等的字符位置和前一个字符最长不重复的位置大小
        Map<Character,Integer> charLocs = new HashMap<>();

        charLocs.put(chars[0],0);

        int preIndex = 0,curIndex;
        int maxLen = 1;

        for (int i = 1; i < chars.length; i++) {

            Integer beforeIndex = charLocs.getOrDefault(chars[i], -1);

            if (beforeIndex < preIndex) {

                curIndex = preIndex;
            }else {
                // 前一个相等位置的下一个为起始位置
                curIndex = beforeIndex + 1;
            }

            charLocs.put(chars[i],i);

            int len = i - curIndex + 1;
            if (len > maxLen) {

                maxLen = len;
            }

            preIndex = curIndex;

        }

        return maxLen;
    }
}
